#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <list>
#include <string.h>
#include <cstring>
#include "CoordinatesVector.h"
#include <assert.h>
#include <time.h>
#include "mpi.h"

using namespace std;

int malloc2dUnsignedShort(unsigned short ***array, int n, int m) 
{
	unsigned short *p = (unsigned short *)malloc(n*m*sizeof(unsigned short));
	if (!p) 
		return -1;

	(*array) = (unsigned short **)malloc(n*sizeof(unsigned short*));
	if (!(*array)) 
	{
		free(p);
		return -1;
	}

	for (int i=0; i<n; i++) 
	(*array)[i] = &(p[i*m]);

	return 0;
}

int free2dUnsignedShort(unsigned short ***array) 
{
	free(&((*array)[0][0]));
	free(*array);
	return 0;
}

bool ArgCheck(int argc, char * argv[])
{
	int FlagInitialized;
	int myId=0;

	MPI_Initialized (&FlagInitialized);
	if(FlagInitialized==1)
		MPI_Comm_rank(MPI_COMM_WORLD,&myId);
	if( (argc != 8 && argc != 10) || ((strcmp(argv[1], "Griewank") != 0) && (strcmp(argv[1], "Ackley") != 0)))
	{
		//if(myId==0)
		{
			printf("Check arguments delivered. \n");
			printf("1st argument - evaluate function - Griewank | Ackley \n");
			printf("2nd argument - size of population \n");
			printf("3th argument - minimum value of member of population \n");
			printf("4th argument - maximum value of member of population \n");
			printf("5th argument - dimension of coordinates vectors \n");
			printf("6th argument - maximum number of iterations \n");
			printf("7th argument - number of repetitions \n");
			printf("8th argument - expected result (optional)\n");
			printf("9th argument - precision - float value (optional - required if 7th argument is delivered)\n");
		}
		return false;
	}
	else
	{
	return true;
	}
}

double evaluateGriewank(CoordinatesVector & Vector)
{
	double sum = 0;
	double mult = 1;
	for(int i=1; i<=Vector.getSize(); ++i)
	{
		sum += Vector.getCoordinateTab()[i-1].getValue() * Vector.getCoordinateTab()[i-1].getValue();
		mult *= cos(Vector.getCoordinateTab()[i-1].getValue()/i);
	}
	double return_value = sum/40 + 1 - mult;
	assert(return_value >= 0);
	return return_value;
}

double evaluateAckley(CoordinatesVector & Vector)
{
	double sum_1 = 0;
	double sum_2 = 0;
	for(int i=0; i<Vector.getSize(); ++i)
	{
		sum_1 += Vector.getCoordinateTab()[i].getValue() * Vector.getCoordinateTab()[i].getValue();
		sum_2 += cos(2*M_PI*Vector.getCoordinateTab()[i].getValue());
	}
	double return_value = -20 * exp( (-0.2)*sqrt(sum_1/Vector.getSize()) ) - exp( sum_2/Vector.getSize()) + 20 + exp(1);
	assert(return_value >= 0);
	return return_value;
}

bool compareCoordinatesVectors(CoordinatesVector &first, CoordinatesVector &second)
{
	if(first.getEvaluation() <= second.getEvaluation())
	{
		return true;
	}
	else
	{
		return false;
	}
}

void prepareSendBuffor(unsigned short **Buffer, std::list<CoordinatesVector> &List, unsigned long PopulationSize, unsigned short CoordinatesVectorDim)
{
	std::list<CoordinatesVector>::iterator it = List.begin();
		for(int i=0; i<PopulationSize; i++)
		{			
			if(it!=List.end())
			{
				for(int j=0; j<CoordinatesVectorDim; j++)
					Buffer[i][j] = it->getCoordinateEncodedValue(j);
			}
			it++;
		}	
}

void consumeReceiveBuffor(unsigned short **Buffer, std::list<CoordinatesVector> &List, unsigned long PopulationSize,  unsigned short CoordinatesVectorDim, short MinCoordValue, short MaxCoordValue, char *argv1)
{
	CoordinatesVector v(CoordinatesVectorDim, MinCoordValue, MaxCoordValue);
	for(int i=0; i<PopulationSize; i++)
	{
		v.initialize(Buffer[i]);
		if(strcmp(argv1, "Griewank") == 0)
			v.setEvaluation(evaluateGriewank(v));
		else if(strcmp(argv1, "Ackley") == 0)
			v.setEvaluation(evaluateAckley(v));
		List.push_back(v);
		for(int j=0; j<CoordinatesVectorDim; j++)
					Buffer[i][j] = v.getCoordinateEncodedValue(j);
	}
	List.sort(compareCoordinatesVectors);
	while(List.size()>(PopulationSize/2))
		List.pop_back();
}

int main(int argc, char * argv[])
{
	srand(time(NULL));
	int myId, numProcs, sendcount, recvcount, source, rc;
	unsigned short** sendBufferEncodedValue;
	unsigned short** receiveBufferEncodedValue;
	MPI_Status stat;
	double startTime, time;
	double bestScore=1000000;
	int bestScoreIterationNumber;
	int FlagInitialized;

	

	if( !ArgCheck(argc, argv))
	{
		MPI_Finalize();
		return 0;
	}

	double ExpectedResult = 0;
	double Precision = 0;
	int Repetitions = atoi(argv[7]);
	if( argc == 10)
	{
		ExpectedResult = atof(argv[8]);
		Precision = atof(argv[9]);
	}

	unsigned long PopulationSize = atol(argv[2]);
	while(PopulationSize%4 != 0)
	{
		PopulationSize += 1;
	}
	
	const unsigned short CoordinatesVectorDim = atoi(argv[5]);
	const short MinCoordValue = atoi(argv[3]);
	const short MaxCoordValue = atoi(argv[4]);

	malloc2dUnsignedShort(&sendBufferEncodedValue, PopulationSize,CoordinatesVectorDim);
	malloc2dUnsignedShort(&receiveBufferEncodedValue, PopulationSize,CoordinatesVectorDim);

	MPI_Init(&argc,&argv);           
    	MPI_Comm_size(MPI_COMM_WORLD,&numProcs);
	MPI_Comm_rank(MPI_COMM_WORLD,&myId);
	//std::cout<<"Uruchomiono proces: "<<myId<<std::endl;
	MPI_Barrier(MPI_COMM_WORLD); 

	startTime = MPI_Wtime();
	int step = 10;
	unsigned int j = 0;
	for(int r=0; r<Repetitions; r++)
	{

		std::list<CoordinatesVector> CoordinatesVectorList;
		std::list<CoordinatesVector> ChildrenList;


		for(unsigned long i=0; i<PopulationSize; ++i)
		{
			CoordinatesVector v(CoordinatesVectorDim, MinCoordValue, MaxCoordValue);
			v.randomInitialize();
			if(strcmp(argv[1], "Griewank") == 0)
				v.setEvaluation(evaluateGriewank(v));
			else if(strcmp(argv[1], "Ackley") == 0)
				v.setEvaluation(evaluateAckley(v));
			CoordinatesVectorList.push_back(v);
		}
		assert(CoordinatesVectorList.size() == PopulationSize);

		unsigned int NumberOfIterations = atoi(argv[6]);
		for(j=0; j<NumberOfIterations; j++)
		{
			//if((numProcs==5) && (j%step == 0) && (j!=0))
			if(((j%step == 0) && (j!=0)) || j==(NumberOfIterations-1))
			{
				int sendCount = PopulationSize*CoordinatesVectorDim;
				if (myId == 0)
				{ 	
					for (int p=1; p<numProcs; p++) 
					{
						MPI_Recv(&(receiveBufferEncodedValue[0][0]), sendCount, MPI_UNSIGNED_SHORT, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &stat);
						consumeReceiveBuffor(receiveBufferEncodedValue, CoordinatesVectorList, PopulationSize, CoordinatesVectorDim, MinCoordValue, MaxCoordValue, argv[1]);
						if(CoordinatesVectorList.begin()->getEvaluation()<bestScore)
						{
							bestScore = CoordinatesVectorList.begin()->getEvaluation();
							bestScoreIterationNumber = j+1;
						}			
					}
					prepareSendBuffor(sendBufferEncodedValue, CoordinatesVectorList, PopulationSize, CoordinatesVectorDim);
					for (int p=1; p<numProcs; p++) 	
						MPI_Send(&(sendBufferEncodedValue[0][0]), sendCount, MPI_UNSIGNED_SHORT, p, 2, MPI_COMM_WORLD);
					//Stop condition
					if(argc == 10)
					{
						if(abs(ExpectedResult - CoordinatesVectorList.begin()->getEvaluation()) <= Precision)
						{
							/*std::cout<<abs(ExpectedResult - CoordinatesVectorList.begin()->getEvaluation())<<" <= "<<Precision<<std::endl;
							std::cout<<"Stop condition, process: "<<myId<<std::endl;
							std::cout<<"Expected result: "<<ExpectedResult<<std::endl;
							std::cout<<"Best: "<<CoordinatesVectorList.begin()->getEvaluation()<<std::endl;
							std::cout<<"Precision: "<<Precision<<std::endl;
							std::cout<<"Sub: "<<ExpectedResult - CoordinatesVectorList.begin()->getEvaluation()<<std::endl;
							std::cout<<"abs(Sub): "<<abs(ExpectedResult - CoordinatesVectorList.begin()->getEvaluation())<<std::endl;
							*/
							break;
						}
					}
				}
				
				else
				{ 
					prepareSendBuffor(sendBufferEncodedValue, CoordinatesVectorList, PopulationSize, CoordinatesVectorDim);
					MPI_Send(&(sendBufferEncodedValue[0][0]), sendCount, MPI_UNSIGNED_SHORT, 0, 1, MPI_COMM_WORLD);
					MPI_Recv(&(receiveBufferEncodedValue[0][0]), sendCount, MPI_UNSIGNED_SHORT, 0, 2, MPI_COMM_WORLD, &stat);
					consumeReceiveBuffor(receiveBufferEncodedValue, CoordinatesVectorList, PopulationSize, CoordinatesVectorDim, MinCoordValue, MaxCoordValue, argv[1]);
					//Stop condition
					if(argc == 10)
					{
						if(abs(ExpectedResult - CoordinatesVectorList.begin()->getEvaluation()) <= Precision)
						{
							//std::cout<<"Stop condition, process: "<<myId<<std::endl;
							break;
						}
					}
				}
				MPI_Barrier(MPI_COMM_WORLD); 
			}
			else
			{
				//selection - erase wrose half of population
				CoordinatesVectorList.sort(compareCoordinatesVectors);

				if(CoordinatesVectorList.begin()->getEvaluation()<bestScore)
				{
					bestScore = CoordinatesVectorList.begin()->getEvaluation();
					bestScoreIterationNumber = j+1;
				}

				while(CoordinatesVectorList.size()>(PopulationSize/2))
				{
					CoordinatesVectorList.pop_back();
				}
			}

			int halfOfCoordinatesVectorListSize = CoordinatesVectorList.size()/2;
			int threadId;
			int k;

			for(k=0; k<halfOfCoordinatesVectorListSize; k++)
			{
				std::list<CoordinatesVector>::iterator crossingIt;
				crossingIt = CoordinatesVectorList.begin();
				for(int c=0; c<k; c++)
					crossingIt++;
				Coordinate * CoordTab_1 = crossingIt->getCoordinateTab();
				crossingIt++;
				Coordinate * CoordTab_2 = crossingIt->getCoordinateTab();
				unsigned short CoordTabLength = crossingIt->getSize();
				CoordinatesVector children_1(CoordinatesVectorDim, MinCoordValue, MaxCoordValue);
				CoordinatesVector children_2(CoordinatesVectorDim, MinCoordValue, MaxCoordValue);
				Coordinate * ChildrenCoordTab_1 = children_1.getCoordinateTab();
				Coordinate * ChildrenCoordTab_2 = children_2.getCoordinateTab();

				for(unsigned short i=0; i<CoordTabLength; ++i)
				{
					//crossing
					unsigned short EncodedValue_1 = (CoordTab_1[i].getEncodedValue() & 0xff00) + (CoordTab_2[i].getEncodedValue() & 0x00ff);

					//mutation...
					unsigned short ProbabilityOfMutation = rand()%10;

					//one of ten children is mutated by one bit
					if( ProbabilityOfMutation == 7)
					{
					    unsigned short flag = 0x0001;
					    unsigned short shift = rand()%16;
					    EncodedValue_1 = EncodedValue_1 ^ (flag << shift);
					}

					ChildrenCoordTab_1[i].setEncodedValue( EncodedValue_1);
					ChildrenCoordTab_1[i].setValue((double)EncodedValue_1 * ((double)(MaxCoordValue - MinCoordValue) / 0xffff) + MinCoordValue);

					//crossing
					unsigned short EncodedValue_2 = (CoordTab_2[i].getEncodedValue() & 0xff00) + (CoordTab_1[i].getEncodedValue() & 0x00ff);

					//mutation...
					ProbabilityOfMutation = rand()%10;

					//one of ten children is mutated by one bit
					if( ProbabilityOfMutation == 7)
					{
						unsigned short flag = 0x0001;
						unsigned short shift = rand()%16;
						EncodedValue_1 = EncodedValue_1 ^ (flag << shift);
					}

					ChildrenCoordTab_2[i].setEncodedValue( EncodedValue_2);
					ChildrenCoordTab_2[i].setValue((double)EncodedValue_2 * ((double)(MaxCoordValue - MinCoordValue) / 0xffff) + MinCoordValue);
				}
				ChildrenList.push_back(children_1);
				ChildrenList.push_back(children_2);
			}
			//children evaluation
			std::list<CoordinatesVector>::iterator it;
			for(it=ChildrenList.begin(); it!=ChildrenList.end(); ++it)
			{
				if(strcmp(argv[1], "Griewank") == 0)
				{
					it->setEvaluation(evaluateGriewank(*it));
				}
				else if(strcmp(argv[1], "Ackley") == 0)
		    		{
					it->setEvaluation(evaluateAckley(*it));
				}
			}
			//add list with new children to population
			CoordinatesVectorList.splice(CoordinatesVectorList.end(), ChildrenList);
		}
		//printf("My iterations: %d\n", j);
	}

	time =  MPI_Wtime() - startTime;
	//printf("End process %d\n",myId);
	if (myId == 0)
	{
		printf("Summary:\n");
		printf("Summary time: %.16g seconds\n", time);
		printf("Best score: %f\n", bestScore);
		printf("Iterations: %d\n", bestScoreIterationNumber);

	}
	free2dUnsignedShort(&sendBufferEncodedValue);
	free2dUnsignedShort(&receiveBufferEncodedValue);
	MPI_Finalize();
	return EXIT_SUCCESS;
}
